package 笔试.奇安信;

//路径获利最大化
public class Demo2 {
    int[][] tool = {{0,1},{1,0},{0,-1},{-1,0}};
    int res = 0;
    public int getMaximumResource(int[][] grid){
        if(grid==null || grid.length==0) return 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j]!=0 && !visited[i][j]){
                    dfs(grid,i,j,grid[i][j],visited);
                }
            }
        }
        return res;
    }

    //tmp记录当前和
    public void dfs(int[][] grid,int x,int y,int tmp,boolean[][] visited){
        if(res<tmp) res = tmp;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x +tool[i][0];
            int newY = y +tool[i][1];
            if(newX< grid.length && newY<grid[0].length && newX>=0
                    && !visited[newX][newY] && grid[newX][newY]!=0){
                dfs(grid,newX,newY,tmp+grid[newX][newY],visited);
            }
        }
        visited[x][y] = false;
    }

}
